This invention improves upon integrated circuits used to perform interval matching. Interval matching hardware has many applications such as pattern and image recognition, but it is used most heavily in classification and access control algorithms for networking systems and storage systems.
In a group of networked systems, contention for common resources such as network bandwidth and stored data require the differentiation between users of the network in order to provide equitable access commensurate with users' privileges and status. In order to differentiate these accesses, network and system administrators classify requests by adminstator-chosen data fields that appear in protocols used to communicate user requests.
Administrators specify this mapping, data to classes of treatment, by a set of range specifications. When the selected data field's value, known also as the search-key, falls into a specified range, the data is considered part of the class associated with that range. Prioritization may take place between overlapping ranges and a given class may specify ranges over many fields. This function, identifying the highest priority interval to which a specific value belongs, is known as interval matching.
To implement interval matching, it is necessary to match a specified value with the highest priority interval containing that value. For example, consider an interval matching circuit configured with the rules 904a, 904b, 904c, 904d illustrated in FIG. 3. The rules are drawn in ascending priority from left to right. If a search-key of value “5” is input to this circuit, so selecting one of the sixteen values 908 possible for the key, the correct functionality requires a result signal identifying the third rule 904c. With every search-key input to the circuit, a classification identifier associated with that class must be returned. With certain restrictions, this matching scheme may be implemented with software on a general purpose computer. These restrictions are: the frequency of user requests must be low and the throughput requirements must be defined only in stochastic terms. A common algorithm for this function is known as an interval tree (See T. H. Cormen et al., “Introduction to Algorithms”, The MIT Press, 1994, pp. 485–487). Such an implementation can be found in U.S. Pat. No. 6,219,667, “Efficient large-scale access control for internet/intranet information systems.” However, when the application produces a high frequency of interval matching requests that require guaranteed processing time, as is the case in networking, a dedicated integrated circuit must be used.
Using prior art, implementing an interval tree in circuit form is not possible without serious limitations. Tree imbalance would turn search bandwidth statistical. Long field widths, as those seen in networking, would make the circuit's datapath width (in particular the logic comparators used to select branches for traversal) insolvable. This type of implementation creates a tradeoff between classification key width and bandwidth, preventing interval trees from scaling. The most efficient circuit-based interval tree known is presented in U.S. Pat. No. 6,633,953, “Range content-addressable memory.” This approach uses a sorted boundary list to store and process the range boundaries of a rule list 904a, 904b, 904c, 904d. This approach suffers from large update times as the entire list needs to be re-sorted with the addition or deletion of a rule. Other integrated circuit approaches have been taken, but without achieving both high performance and high density (number of intervals/per unit of silicon area). Some approaches, such as ternary content addressable memory (TCAM) not only suffer from low-density and high power, but from a highly statistical capacity as well. In this case, because ranges must be represented by groups of data-mask pairs, large inner products form when several data fields must be analyzed (See Gupta, Algorithms for Routing Lookup and Packet classification, Stanford University Ph.D. Thesis, Page 135).
The work herein represents a significant advance in circuits for interval matching by simultaneously solving the problems of deterministic bandwidth and capacity, high performance and high density, and scaling to large key widths, as needed by networking applications.